import javax.swing.tree.TreeNode;

public class Test {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, inorder, 0, preorder.length-1, 0 ,inorder.length-1);
    }

    public TreeNode build(int[] preorder, int[] inorder, int preStart, int preEnd, int inoStart, int inoEnd){
        if (preStart > preEnd && inoStart > inoEnd){
            return null;
        }
        int val = preorder[preStart];
        TreeNode root = new TreeNode(val);
        int index = 0;
        for (int i = 0; i <= preEnd; i++){
            if (inorder[i] == val){
                index = i;
                break;
            }
        }
        int leftSize = index - inoStart;
        root.left = build(preorder, inorder, preStart+1, preStart+leftSize, inoStart, index-1);
        root.right = build(preorder, inorder, preStart+leftSize+1, preEnd, index+1, inoEnd);
        return root;
    }

    public boolean isBalanced(TreeNode root) {
        return recur(root) != -1;
    }

    public int recur(TreeNode root){
        if (root == null){
            return 0;
        }
        int left = recur(root.left);
        if (left == -1){
            return -1;
        }
        int right = recur(root.right);
        if (right == -1){
            return -1;
        }
        return Math.abs(left - right) < 2 ? Math.max(left,right)+1 : -1;
    }
}
